package com.mdnote.practice.binary_tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/30
 * @description 二叉树的层序遍历
 */
public class LeetCode102 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> list = new ArrayList<>();
        _levelOrder(0, root, list);
        return list;
    }

    private void _levelOrder(int level, TreeNode node, List<List<Integer>> list) {
        // Terminator
        if (node == null) {
            return;
        }
        // Process
        if (list.size() < level + 1) {
            list.add(new ArrayList<>());
        }
        list.get(level).add(node.val);

        _levelOrder(level + 1, node.left, list);
        _levelOrder(level + 1, node.right, list);
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
